#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=189 lang=cpp
 *
 * [189] 轮转数组
 */

// @lc code=start
class Solution {
public:
    // 采用取逆的方式
    // void rotate(vector<int>& nums, int k) {
    //     int sz = nums.size(); k = k % sz;
    //     reverse(nums.begin(), nums.end());
    //     reverse(nums.begin(), nums.begin() + k);
    //     reverse(nums.begin() + k, nums.end());
    // }

    // 一个更加巧妙的方法
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    void rotate(vector<int>& nums, int k) {
        int sz = nums.size(); k = k % sz;
        int count = gcd(k, sz);
        for (int i = 0; i < count; i++) {
            int current = i, pre = nums[i];
            do {
                int next = (current + k) % sz;
                swap(pre, nums[next]);
                current = next;
            } while (i != current);
        }

    }

};
// @lc code=end

